#include "SudokuSolve.h"

SudokuSolve::SudokuSolve()
{

}

bool SudokuSolve::solve(int answer[9][9], const int puzzle[9][9])
{
    int tmp[9][9];
    int empty[9 * 9] = {-1};
    int cnt = 0;
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            tmp[i][j] = puzzle[i][j];
            if(puzzle[i][j] == 0)
            {
                empty[cnt] = i * 9 + j;
                cnt++;
            }
        }
    }

    bool find = false;
    int i = 0;
    int j = 0;
    int k = 0;
    int m = 0;

    for (; m < cnt;)
    {
        i = empty[m] / 9;
        j = empty[m] % 9;

        find = false;
        if(tmp[i][j] == 0)
        {
            k = 9;
        }
        else
        {
            k = tmp[i][j] - 1;
        }
        for (; k > 0; k--)
        {
            if(isOk(tmp, i, j, k))
            {
                tmp[i][j] = k;
                find = true;
                m++;
                break;
            }
        }
        if(!find)
        {
            tmp[i][j] = 0;
            m--;
        }
    }
    if(m == cnt)
    {
        for (int i = 0; i < 9; i++)
        {
            for (int j = 0; j < 9; j++)
            {
                answer[i][j] = tmp[i][j];
            }
        }
        return true;
    }
    else
    {
        return false;
    }
}

bool SudokuSolve::solve2(int answer[9][9], const int puzzle[9][9])
{
    int tmp[9][9];
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            tmp[i][j] = puzzle[i][j];
        }
    }

    bool b = solve(tmp, puzzle, 0);
    if(!b)
    {
        return false;
    }
    for (int i = 0; i < 9; i++)
    {
        for (int j = 0; j < 9; j++)
        {
            answer[i][j] = tmp[i][j];
        }
    }
    return true;
}

bool SudokuSolve::isOk(const int answer[9][9], int i, int j, int num)
{
    if(num == 0)
    {
        return false;
    }
    for (int k = 0; k < 9; k++)
    {
        if((k != j) && (answer[i][k] == num))
        {
            return false;
        }
    }

    for (int k = 0; k < 9; k++)
    {
        if((k != i) && (answer[k][j] == num))
        {
            return false;
        }
    }

    int r = i / 3;
    int w = j / 3;
    for (int m = 0; m < 3; m++)
    {
        for (int n = 0; n < 3; n++)
        {
            if((r * 3 + m != i) && (w * 3 + n != j) && answer[r * 3 + m][w * 3 + n] == num)
            {
                return false;
            }
        }
    }
    return true;
}

bool SudokuSolve::isAllOk(const int answer[9][9])
{
    bool flag[10];
    for (int i = 0; i < 9; i++)
    {
        for (int k = 1; k <= 9; k++)
        {
            flag[k] = false;
        }
        for (int j = 0; j < 9; j++)
        {
            if(answer[i][j] == 0)
            {
                return false;
            }
            flag[answer[i][j]] = true;
        }
        for (int k = 1; k <= 9; k++)
        {
            if(flag[k] == false)
            {
                return false;
            }
        }
    }

    for (int i = 0; i < 9; i++)
    {
        for (int k = 1; k <= 9; k++)
        {
            flag[k] = false;
        }
        for (int j = 0; j < 9; j++)
        {
            flag[answer[j][i]] = true;
        }
        for (int k = 1; k <= 9; k++)
        {
            if(flag[k] == false)
            {
                return false;
            }
        }
    }

    for (int i = 0; i < 3; i++)
    {
        for (int j = 0; j < 3; j++)
        {
            for (int k = 1; k <= 9; k++)
            {
                flag[k] = false;
            }
            for (int m = 0; m < 3; m++)
            {
                for (int n = 0; n < 3; n++)
                {
                    flag[answer[i * 3 + m][j * 3 + n]] = true;
                }
            }
            for (int k = 1; k <= 9; k++)
            {
                if(flag[k] == false)
                {
                    return false;
                }
            }
        }
    }
    return true;
}

bool SudokuSolve::solve(int answer[9][9], const int puzzle[9][9], int num)
{
    if(num < 0)
    {
        return false;
    }
    if(num > 80)
    {
        return true;
    }

    int i = num / 9;
    int j = num % 9;
    if(puzzle[i][j] != 0)
    {
        int next = 9 * 9;
        for (int m = num + 1; m < 9 * 9; m++)
        {
            if(puzzle[m / 9][m % 9] == 0)
            {
                next = m;
                break;
            }
        }
        return solve(answer, puzzle, next);
    }
    int k = 0;
    if(answer[i][j] == 0)
    {
        k = 9;
    }
    else
    {
        k = answer[i][j] - 1;
    }
    for (; k > 0; k--)
    {
        if(isOk(answer, i, j, k))
        {
            answer[i][j] = k;
            int next = 9 * 9;
            for (int m = num + 1; m < 9 * 9; m++)
            {
                if(puzzle[m / 9][m % 9] == 0)
                {
                    next = m;
                    break;
                }
            }
            return solve(answer, puzzle, next);
        }
    }
    int last = -1;
    for (int m = num - 1; m > 0; m--)
    {
        if(puzzle[m / 9][m % 9] == 0)
        {
            last = m;
            break;
        }
    }
    answer[i][j] = 0;
    return solve(answer, puzzle, last);
}
